package tree;

import node.Node;

import java.util.*;

/**
 * @author Yakiv Tymoshenko
 * @since 14.10.12
 */
public class TreePrinter {

    private TreeScanner treeScanner;
    private Map<Integer, List<Node>> levelNodesMap;

    public TreePrinter(TreeScanner treeScanner) {
        this.treeScanner = treeScanner;
        treeScanner.visitNodes();
        initMap();
    }

    public String printNodePositions() {
        StringBuilder result = new StringBuilder();
        List<Boolean> nodePositions;
        for (int i = 0; i < treeScanner.getTreeHeight(); i++) {
            nodePositions = nodePositions(i + 1);
            for (Boolean flag : nodePositions) {
                if (flag) {
                    result.append(String.valueOf(1));
                } else {
                    result.append(String.valueOf(0));
                }
            }
            result.append("\n");
        }
        result.append("\n");
        return result.toString();
    }

    public String printTree() {
        StringBuilder stringBuilder;
        Stack<String> stack = new Stack<String>();
        List<Boolean> nodePositions;
        List<Node> nodes;
        for (int i = treeScanner.getTreeHeight(); i > 0; i--) {
            stringBuilder = new StringBuilder();
            nodePositions = nodePositions(i);
            nodes = levelNodesMap.get(i);
            int j = 0;
            int nodeIndex;
            for (Boolean flag : nodePositions) {
                if (flag) {
                    if (j < nodes.size() && nodes.get(j) != null) {
                        nodeIndex = nodes.get(j).getIndex();
                        stringBuilder.append(nodeIndex);
                    } else {
                        stringBuilder.append(" ");
                    }
                    j++;
                } else {
                    stringBuilder.append(" ");
                }
            }
            stringBuilder.append("\n");
            stack.push(stringBuilder.toString());
        }

        StringBuilder result = new StringBuilder();
        while (!stack.empty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }

    // TODO If node index > 1 digit, the tree structure shifts incorrectly
    // Maybe, should reserv 3 digits per node
    private List<Boolean> nodePositions(int level) {
        List<Boolean> result = new ArrayList<Boolean>();
        final int verticesCount = (int) Math.pow(2, level - 1);
        if (level == treeScanner.getTreeHeight()) {     // last row
            int j = 0; // vertice index
            while (j < verticesCount) {
                result.add(true);
                j++;
                // spaces between siblings
                for (int k = 0; k < 3; k++) {
                    result.add(false);
                }
                result.add(true);
                j++;
                result.add(false);  // space between cousins
            }
        } else {
            // Assume that each node of current level is parent of 2 vertices from the next level
            // Place parent between it's children
            int leftChildPosition;
            int rightChildPosition;
            int parentPosition;
            List<Boolean> nextRow = nodePositions(level + 1);
            int nextLevelRowIterator = 0;
            int firstSpacePosition = 0;
            for (int i = 0; i < verticesCount; i++) {
                leftChildPosition = findNextChildPosition(nextRow, nextLevelRowIterator);
                nextLevelRowIterator = leftChildPosition + 1;

                rightChildPosition = findNextChildPosition(nextRow, nextLevelRowIterator);
                nextLevelRowIterator = rightChildPosition + 1;

                parentPosition = (leftChildPosition + rightChildPosition) / 2;
                addSpaces(result, firstSpacePosition, parentPosition);
                result.add(parentPosition, true);
                firstSpacePosition = parentPosition + 1;
            }
        }
        return result;
    }

    private int findNextChildPosition(List<Boolean> row, int startPosition) {
        int result;
        if (row.get(startPosition)) {
            result = startPosition;
        } else {
            int i = startPosition + 1;
            while (!row.get(i) && i < row.size()) {
                i++;
            }
            result = i;
        }
        return result;
    }

    private void addSpaces(List<Boolean> row, int from, int to) {
        for (int i = from; i < to; i++) {
            row.add(i, false);
        }
    }

    private void initMap() {
        levelNodesMap = new TreeMap<Integer, List<Node>>();
        putInMap(1);
    }

    private void putInMap(int level) {
        if (level == 1) {
            levelNodesMap.put(level, new ArrayList<Node>(Arrays.asList(treeScanner.getTree().getRoot())));
        } else {
            List<Node> nodes = new ArrayList<Node>();
            for (Node node : levelNodesMap.get(level - 1)) {
                final Node left = node != null ? node.getLeft() : null;
                final Node right = node != null ? node.getRight() : null;
                nodes.add(left);
                nodes.add(right);
            }
            levelNodesMap.put(level, nodes);
        }
        final int nextLevel = level + 1;
        if (nextLevel <= treeScanner.getTreeHeight()) {
            putInMap(nextLevel);
        }
    }
}
